/**
 * @file   QuickSort.h
 * @author WinterMelonCDY <wintermeloncdy@wintermeloncdy-VirtualBox>
 * @date   Mon Dec 13 21:54:24 2021
 * 
 * @brief  
 * 
 * 
 */

#include<vector>
#include<iostream>
#include<random>
#include<ctime>

using namespace std;


template<typename Comparable>
void quicksort(vector<Comparable> &A,int begin,int end,int type);
template<typename Comparable>
int middle_index(const vector<Comparable> &A,int a, int b,int c);



template<typename Comparable>
void insertsort(vector<Comparable> &A,int begin, int end)
{
    int len=end-begin+1;
    for(int i=0;i<len;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(A[begin+j]>A[begin+j+1])
            std::swap(A[begin+j+1],A[begin+j]);
            else
            break;
        }
    }
}

template<typename Comparable>
void sort(vector<Comparable> &A, int type)
{
    quicksort(A,0,A.size()-1,type);
}//type==0 means random number & type==1 means middle number

template<typename Comparable>
void quicksort(vector<Comparable> &A,int begin,int end,int type)
{
    int len=end-begin+1;
    
    if(len<=10)
    {
        insertsort(A,begin,end);
    }
    else
    {
        int prior;
        if(type==1) prior= middle_index(A,begin,begin/2+end/2,end-1);
        else prior= begin+ rand()% (len-1);

        swap(A[prior],A[end]);

        int i=begin-1;int j=end;
            while(1)
        {
            while(A[++i]<=A[end]&&i<=end-1){}
            while(A[--j]>A[end]&&j>=begin+1){}
            if(i<j) swap(A[i],A[j]);
            else break;
        }
        swap(A[i],A[end]);
        
        quicksort(A,begin,i-1,type);
        quicksort(A,i+1,end,type);

    }

}

template<typename Comparable>
int middle_index(const vector<Comparable> &A,int a, int b,int c)
{
    if(A[a]>=A[b]&&A[b]>=A[c]) return b;
    if(A[c]>=A[b]&&A[b]>=A[a]) return b;
    if(A[b]>=A[c]&&A[c]>=A[a]) return c;
    if(A[a]>=A[c]&&A[c]>=A[b]) return c;
    if(A[b]>=A[a]&&A[a]>=A[c]) return a;
    if(A[c]>=A[a]&&A[a]>=A[b]) return a;
    else return 0;
}

